%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Definici�n del tipo de documento.                                           %
% Posibles tipos de papel: a4paper, letterpaper, legalpapper                  %
% Posibles tama�os de letra: 10pt, 11pt, 12pt                                 %
% Posibles clases de documentos: article, report, book, slides                %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[a4paper,11pt]{article}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Los paquetes permiten ampliar las capacidades de LaTeX.                     %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Paquete para inclusi�n de gr�ficos.
\usepackage{graphicx}

% Paquete para definir la codificaci�n del conjunto de caracteres usado
% (latin1 es ISO 8859-1).
\usepackage[utf8]{inputenc}

% Paquete para definir el idioma usado.
\usepackage[spanish]{babel}
\usepackage{float}

% T�tulo principal del documento.
\title{		\textbf{Trabajo pr\'actico 1: \\ Conjunto de Instrucciones MIPS \\[3ex]}}

% Informaci�n sobre los autores.
\author	{ 	Badano Juan Ignacio, \textit{Padr\'on Nro. 90.241}                      \\
            \texttt{ j\_badano@hotmail.com }                                            \\
            Liva Mar\'ia Eugenia, \textit{Padr\'on Nro. 86.123}                     	\\
            \texttt{ m.eugenia@liva.net.ar }                                            \\
            Retyk Federico, \textit{Padr\'on Nro. 90.597}                     		\\
            \texttt{ fede.retyk@gmail.com }                                             \\[3ex]
            \normalsize{Grupo Nro. X - 1er. Cuatrimestre de 2011}                       \\
            \normalsize{66.20 Organizaci\'on de Computadoras}                           \\
            \normalsize{Facultad de Ingenier\'ia, Universidad de Buenos Aires}          \\
       }

\date{Jueves 05 de mayo de 2011}

\begin{document}

% Inserta el t�tulo.
\maketitle

% Quita el n�mero en la primer p�gina.
\thispagestyle{empty}

% Resumen
\begin{abstract}
El presente informe se corresponde al trabajo pr\'actico n\'umero 1 de la asignatura 66.20 Organizaci\'on de Computadoras. El trabajo consisti\'o en desarrollar un programa portable con el objetivo de familiarizarse con el conjunto de instrucciones MIPS32 y el concepto de ABI.
\end{abstract}

\newpage

\tableofcontents

\newpage

\section{Introducci\'on}

MIPS (Microprocessor without Interlocked Pipeline Stages) es un procesador con arquitectura RISC (reduced instruction set computer) desarrollado por MIPS Technologies. Este tipo de procesadores se encuentra en muchos sistemas embebidos y dispositivos de la actualidad como consolas de videojuegos, routers, etc. En particular, debido a que los dise\~{n}adores crearon un conjunto de instrucciones tan claro, los cursos sobre arquitectura de computadoras en unviersidades y escuelas t\'ecnicas a menudo se basan en la arquitectura MIPS.
\\[3ex]
Existen m\'ultiples versiones de \'este procesador, siendo los m\'as recientes MIPS32 y MIPS64, implementadas para 32 y 64 bits, respectivamente. 
\\[3ex]
El lenguaje ensamblador o assembler  es un lenguaje de programaci\'on de bajo nivel para los computadores, microprocesadores, microcontroladores, y otros circuitos integrados programables. Implementa una representaci\'on simb\'olica de los c\'odigos de m\'aquina binarios y otras constantes necesarias para programar una arquitectura dada de CPU y constituye la representaci\'on m\'as directa del c\'odigo m\'aquina espec\'ifico para cada arquitectura legible por un programador. Esta representaci\'on es usualmente definida por el fabricante de hardware, y est\'a basada en los mnem\'onicos que simbolizan los pasos de procesamiento (las instrucciones), los registros del procesador, las posiciones de memoria, y otras caracter\'isticas del lenguaje. Cada lenguaje ensamblador es espec\'ifico a cierta arquitectura. En este trabajo utilizaremos la arquitectura MIPS32 con su conjunto de instrucciones (ISA) y su lenguaje ensamblador.
\\[3ex]
Un ABI (application binary interface, o traducido al espa\~{n}ol, interfaz binaria de aplicaci\'on) describe la interfaz de bajo nivel entre una aplicaci\'on y el sistema operativo, entre una aplicaci\'on y sus bibliotecas, o entre un procesador y los programas que se correr\'an en \'el.
\\[3ex]
\'Este \'ultimo caso es el que abordaremos en el presente trabajo pr\'actico, en particular, nuestra ABI describir\'a la interfaz entre el procesador MIPS32, mencionado anteriormente, y los programas que correr\'an sobre \'el. Esto nos garantiza la compatibilidad de estos programas entre s\'i. 
\\[3ex]
Un ABI es distinto de una API (interfaz de programaci\'on de aplicaciones) en que un API define la interfaz entre el c\'odigo fuente y bibliotecas, por esto ese mismo c\'odigo fuente compilar\'a en cualquier sistema que soporte esa API, mientras que un ABI permite que un c\'odigo objeto compilado funcione sin cambios sobre cualquier sistema usando un ABI compatible.
\\[3ex]
El objetivo del trabajo pr\'actico es familiarizarse con el conjunto de instrucciones MIPS32 y el concepto de ABI, para ello desarrollaremos un programa portable, el cual se presentar\'a con m\'as detalle en posteriores incisos. 

\section{Desarrollo}

El programa que se implement\'o fue una aplicaci\'on que calcula el MCM (M\'inimo Com\'un Multiplo) y el MCD (M\'aximo Com\'un Denominador) de dos n\'umeros enteros. Para ello se program\'o la captura de opciones y parametros, y la devoluci\'on de resultados en lenguaje C de alto nivel; y las funciones MCM y MCD, por separado en lenguaje ensamblador para MIPS32. Una vez obtenido los c\'odigos, se enlazaron y se repiti\'o los procedimientos del anterior trabajo pr\'actico para emular y ejecutar el programa en MIPS32. 

\section{Dise\~{n}o y detalles de implementaci\'on}

\subsection{Recursos utilizados}

Para resolver el problema planteado utilizamos las herramientas del trabajo pr\'actico anterior, GXemul, para emular un entorno MIPS y el sistema operativo NetBSD. Tambi\'en utilizamos el programa SPIM. \'Este programa es un simulador que ejecuta programas en lenguaje ensamblador para los computadores basados en los procesadores MIPS.  
\\[3ex]
Para implementar el programa utilizamos el lenguaje de programaci\'on C, la ABI y lenguaje ensamblador de MIPS, y el sistema operativo Linux. Para este informe utilizamos \LaTeX{}.

\subsection{Dise\~{n}o}

Como mencionamos anteriormente, el programa implementado fue una aplicaci\'on que calcula el MCM y el MCD de dos numeros enteros.
\\[3ex]
Al ser un programa de consola el dise\~{n}o es bastante sencillo, el formato del comando se compone por: la invocaci\'on al programa inmediatamente las opciones con sus argumentos y por \'ultimo los n\'umeros M y N.

\begin{center}
\texttt{common [options] M N}
\end{center}

El programa, sin especificar opciones, devuelve por consola el MCD y en la siguiente linea el MCM.
\\[3ex]
Las opciones pueden ser:
\begin{itemize}
 \item -h, --help : Imprime la version del programa.
 \item -v, --version : El cual imprime informaci\'on de como usar el programa.
 \item -o, --output : Se especifica un archivo de salida. En este caso no se imprime el resultado por consola sino que se imprime en el archivo de salida especificado con el mismo formato.
 \item -d, --divisor : Solo retorna el divisor.
 \item -m, --multiple: Solo retorna el m\'ultiplo.
\end{itemize}
Cabe destacar que si se invoca el programa con n\'umeros inv\'alidos, es decir, n\'umeros fuera del rango [2 , MAXINT], \'este retorna un error.

\subsection{Implementaci\'on}

\subsubsection{API} 

Como mencionamos anteriormente gran parte de la aplicaci\'on se program\'o en lenguaje C, sin embargo, las funciones mcd (M,N) y mcm(M,N) se implementaron en lenguaje ensamblador de MIPS32, para proveer soporte espec\'ifico en nuestra plataforma principal de desarrollo, NetBSD/pmax.
\\[3ex]
Para implementar la funci\'on mcd (m\'aximo com\'un divisor) utilizamos el algoritmo recursivo de Euclides, y para implementar la funci\'on mcm (m\'inimo com\'un m\'ultiplo) utilizamos lo programado para la funci\'on mcd de la siguiente forma:

\begin{center}
\texttt{ mcm(M,N) = M.N/mcd(M,N) }
\end{center}

Es decir, la funci\'on mcm hace una llamada a mcd en su c\'odigo.
\\[3ex]
Por \'ultimo, el programa en C procesa los argumentos de entrada con getopt\_long, y seg\'un las opciones ingresadas llama a la o las funciones necesarias e imprime por pantalla o archivo de salida.

\subsubsection{Portabilidad}

Para proveer el grado de portabilidad necesario se tuvo que implementar las funciones mcd y mcm no solo en assembler, sino tambi\'en en lenguaje C pensado para dar soporte gen\'erico a aquellos entornos que carezcan de una versi\'on m\'as espec\'ifica. 

\subsubsection{ABI}

Utilizamos la ABI explicada en clase, en particular la convenci\'on de pasaje de par\'ametros: los argumentos correspondientes a los registros \$a0-\$a3 se almacenaron por el callee en los 16 bytes dedicados de la secci\'on "function call argument area".

\subsubsection{C\'odigo y algoritmos}

Como se ha mencionado el algoritmo utilizado para programar la funci\'on mcd fue el algoritmo de Euclides en su versi\'on recursiva, aqu\'i mostramos un pseudoc\'odigo del mismo:

\begin{tabbing}
------- \= ------ \= ----- \= ... \kill
mcd(M,N):\\ 
\> si N = 0 devuelve M \\
\> sino devuelve mcd(N, M mod N)\\
\end{tabbing}

\subsection{Portabilidad y compilaci\'on }

El programa implementado puede ser compilado tanto en assembler de NetBSD para MIPS32 como en su versi\'on en lenguaje C, lo cual provee un grado de portabilidad. 
\\[3ex]
Se implement\'o esta posibilidad a trav\'es de un Makefile. Para compilar el programa con sus archivos en assembler de NetBSD, es necesario ejecutar el siguiente c\'odigo:
\begin{center}
\texttt{ \$ make mips }
\end{center}
Si en cambio deseamos compilarlo en alguna otra arquitectura, debemos ingresar el comando:
\begin{center}
\texttt{ \$ make} o bien, \texttt{ \$ make generic } 
\end{center}


\newpage
\section{Corridas de prueba y resultados obtenidos }

A continuaci\'on presentamos una corrida de prueba de la implementaci\'on, compilación y ejecución desde NetBSD.

% Tenemos que incluir una imagen de la ejecucion cuando hallamos terminado, en formato EPS (Encapsulated Postscript).
\begin{figure}[H]
\begin{center}
\includegraphics[width=0.9\textwidth]{make.eps}
\end{center}
\caption{Compilación y construcción del ejecutable. Salida del parámetro -h o --help} \label{fig001}
\end{figure}

\begin{figure}[H]
\begin{center}
\includegraphics[width=0.9\textwidth]{output.eps}
\end{center}
\caption{Diversas formas de uso de la opción -o para salida de resultados a un archivo} \label{fig002}
\end{figure}

\begin{figure}[H]
\begin{center}
\includegraphics[width=0.9\textwidth]{192.eps}
\end{center}
\caption{Ejecución del caso de prueba en que los valores de entrada son 192 y 256} \label{fig003}
\end{figure}

Puede verse que la soluci\'on responde correctamente a los ejemplos suministrados por los docentes, tanto en sus funcionalidades opcionales como en la principal, es decir, la ejecuci\'on imprime en pantalla lo que se ped\'ia en las pruebas de la c\'atedra.

\newpage
\section{Diagramas de Stack}

Stack de función \textbf{mcm} (non-leaf)

\begin{figure}[!htp]
\begin{center}
\includegraphics[width=0.6\textwidth]{mcm-stack.eps}
\end{center}
\caption{Stack frame de mcm}
\end{figure}

Stack de función \textbf{mcd} (leaf)

\begin{figure}[!htp]
\begin{center}
\includegraphics[width=0.6\textwidth]{mcd-stack.eps}
\end{center}
\caption{Stack frame de mcd}
\end{figure}

\section{Conclusiones}

A partir de este trabajo adquirimos cierta experiencia en programaci\'on en assembler para MIPS32, lo cual nos sirvi\'o para entender conceptos de la materia como el set de instrucciones de un procesador (ISA), el concepto de interfaz binaria de aplicaci\'on (ABI), la organizaci\'on interna de un procesador y la interacci\'on de los programas ensamblados por separado y enlazados posteriormente por el linker.

% Citas bibliogr�ficas.
\begin{thebibliography}{99}

\bibitem{HEN00} J. L. Hennessy and D. A. Patterson, ``Computer Architecture. A Quantitative
Approach,'' 3ra Edici\'on, Morgan Kaufmann Publishers, 2000.
\bibitem{HEN01} Grupo de la materia http://groups.yahoo.com/group/orga6620/
\bibitem{HEN02} ABI http://www.sco.com/developers/devspecs/mipsabi.pdf
\bibitem{HEN03} Wikipedia en.wikipedia.org


\end{thebibliography}

\end{document}
